Keep and carry on.
post @ 2023-12-23

信息安全数学基础

课程实验报告

实验报告(一)

系 别: 网络空间安全系

班 级: secret!

姓 名: secret!

学 号: secret!

实验时间: 2023年10月17日

指导老师: secret!

湖南大学信息科学与工程学院

  1. 实验内容

  1. 实验目标

理解求逆元和欧拉函数原理以及证明,并利用c++代码实现,并在基础上优化

  1. 实验原理

3.1 求逆元

根据教材内容证明过程可知,求解逆元有两种方法:

方法一:定义a*a’%m=1

方法二:广义欧几里得除法s*a+t*m=1,a’=s

3.2 求欧拉函数

结合欧拉函数定义和求解公式可知,求解过程如下:

遍历小于n的素数,减去能整除这些素数的个数,遍历完毕如果还是素数则进一步减去自身的倍数,剩下的个数是欧拉函数

  1. 实验设计

4.1求逆元

4.1.1方法一:定义

4.1.1.1 代码思路

(1)首先,从标准输入中读取两个整数a和m。

(2)定义一个变量inv_a,并初始化为-1。这个变量用来存储逆元。

(3)使用一个for循环,从1到m-1遍历所有可能的逆元。

(4)在循环中,通过判断(a * i) % m == 1来找到逆元。如果找到了逆元,将其赋值给inv_a,并使用break语句跳出循环。

(5)最后,将逆元inv_a输出到标准输出。

这段代码的时间复杂度为O(m),因为需要遍历所有可能的逆元,适合m较小时遍历求解。

4.1.2 方法二:

4.1.2.1 代码思路

使用了扩展欧几里得算法来计算两个整数的逆元:

(1)定义了一个函数exgcd,用于计算a和b的最大公约数,并且通过引用参数x和y返回扩展欧几里得算法的结果。

在exgcd函数中,首先判断b是否为0,如果是,则将x设置为1,y设置为0,并返回a作为最大公约数。a*x+b*y=a

如果b不为0,则递归调用exgcd函数,将b和a%b作为参数,并将y和x的值交换,以便在递归返回时正确计算x和y的值。

在递归返回后,通过以下公式计算x和y的值:y -= a/b * x;

最后,exgcd函数返回最大公约数d。

(2)在main函数中,首先从输入中读取两个整数a和m。

然后定义了两个变量x和y,用于存储逆元的计算结果。

调用exgcd函数,将a和m作为参数,并将计算结果存储在x和y中。

接下来,通过判断最大公约数d是否等于1来确定是否存在逆元。如果d不等于1,则输出”没有逆元”。

如果d等于1,则计算逆元的值,并使用取模运算确保结果在范围(0, m)内,然后输出结果(x%m+m)%x,因为x就是逆元,但是这样处理保证数值为正

4.1.2.2 x和y是什么

在这段代码中,x和y是exgcd函数的参数,它们是用来存储扩展欧几里得算法计算过程中的中间结果。

具体来说,x和y分别表示方程ax + by = d中的未知数。在扩展欧几里得算法中,我们通过递归的方式计算最大公约数d,并且在计算过程中更新x和y的值。

在函数的开始,我们将x和y的初始值设为1和0,这是因为当b等于0时,方程变为ax + 0y = a,所以x的系数为1,y的系数为0。

然后,在递归调用中,我们将y赋值给x,将a % b赋值给y,并且通过递归计算最大公约数d。最后,我们通过y -= a / b * x来更新y的值,以便在递归返回时得到正确的结果。

因此,x和y在这段代码中起到了存储中间结果的作用,用于计算最大公约数和更新系数的值。

举一个例子:

当我们使用扩展欧几里得算法来计算两个数的最大公约数时,我们需要通过递归调用来更新变量 x 和 y 的值。交换 x 和 y 的位置是为了确保在递归返回时得到正确的结果。

假设我们要计算 a = 30 和 b = 18 的最大公约数,并找到满足方程 ax + by = d 的整数解。

首先,我们进行第一次递归调用 exgcd(b, a % b, y, x),其中 b = 18,a % b = 12。我们将 y 和 x 的引用传递给递归调用。

在递归调用中,我们再次进行递归调用 exgcd(b, a % b, y, x),其中 b = 12,a % b = 6。这一次,我们将 y 和 x 的引用传递给递归调用。

在递归调用中,我们再次进行递归调用 exgcd(b, a % b, y, x),其中 b = 6,a % b = 0。这一次,我们将 y 和 x 的引用传递给递归调用。

由于 a % b = 0,递归调用结束,我们开始递归返回。在递归返回的过程中,我们更新 x 和 y 的值。

在第一次递归返回时,我们有 x = 1,y = 0。这是因为在 b = 6 和 a % b = 0 的情况下,方程 ax + by = d 变为 6x + 0y = 6,所以 x 的系数为 1,y 的系数为 0。

在第二次递归返回时,我们有 x = 0,y = 1。这是因为在 b = 12 和 a % b = 6 的情况下,方程 ax + by = d 变为 12x + 6y = 6,所以 x 的系数为 0,y 的系数为 1。

在第三次递归返回时,我们有 x = 1,y = -2。这是因为在 b = 18 和 a % b = 12 的情况下,方程 ax + by = d 变为 18x + 12y = 6,所以 x 的系数为 1,y 的系数为 -2。

最终,我们得到的最大公约数为 d = 6,并且满足方程 ax + by = d 的整数解为 x = 1,y = -2。

通过交换 x 和 y 的位置,我们可以确保在递归返回时,x 对应的是方程 ax + by = d 中 x 的系数,y 对应的是方程中 y 的系数。这样,我们可以得到正确的结果。

4.1.2 测试优化

但是在测试时发现,当n输入为很大超出INT_MAX时,根据范围对数据类型进行修改,改为long long类型:

4.2 欧拉函数

4.2.1代码思路

(1)初始化一个变量ans为n,用于保存最终的欧拉函数值。

(2)使用一个循环从2开始遍历到n的平方根。在循环中,判断n是否能被当前的循环变量i整除,如果可以整除,则说明i是n的一个素因子。

(3)如果i是n的素因子,将ans减去ans/i,这是因为ans/i表示小于等于n且与n互质的数中,能被i整除的数的个数。

(4)在一个内部的while循环中,将n不断除以i,直到n不能再被i整除为止。这是为了将n中的所有i素因子全部约掉。

(5)如果循环结束后,n仍然大于1,则说明n本身是一个素数,将ans减去ans/n。

(6)最后,返回ans作为欧拉函数的值。

总结起来,这段代码通过遍历n的素因子,将与n互质的数的个数逐步减去,最终得到欧拉函数的值。

4.2.2 测试优化

但是在测试时发现,当n输入为10^10时结果超出INT_MAX,所以根据范围对数据类型进行修改,改为long long类型:

  1. 实验结果

5.1求逆元

5.1.1编译

方法一编译:

方法二编译:

5.1.2 运行

测试书中样例:

输入a=2,m=7,输出逆元4;

输入a=635,m=737,输出逆元513

输入很大的数:

虽然结果是没有逆元是正确的,但是其实是巧合,因为INT_MAX=2147483646也跟2不互质没有逆元,输入a=1时同理,因为1的逆元是1本身

当将m换成与2互质且大于INT_MAX的数理应有逆元,但是输出“没有逆元”错误

但是即使修改成long long类型还是运行3个小时还无法算出结果,但是在方法二中可以输出结果

方法二long long优化代码输出结果:

经定义a*a’%m=1验证2*11666666666667=23333333333334-23333333333333=1

5.2欧拉函数

5.2.1编译:

5.2.2运行测试:

输入10

输入100:

输入10^10:

超出INT_MAX范围,输出错误

优化后:(将int改为long long)

以上结果验证均正确

六、总结

本次实验用c++编程实现了求解逆元和欧拉函数。

其中根据逆元的两种定义对应了两种求解思路,分别是尝试取余为1以及广义欧几里得算法。根据两种思路可以确定对应的求解适应背景,尝试法适用于较小数,而广义欧几里得算法适用于较大整数。在计算时产生中间结果较大不易用int类型保存,可优化为long long保存变量值。

求解欧拉函数,根据其基本定义是不大于整数n的素因子个数。那么遍历计数找其素因子,并将与n互质的数的个数逐步减去,最终得到欧拉函数的值。同理,在计算时产生中间结果较大不易用int类型保存,可优化为long long保存变量值,输入相同较大数进行测试看出优化后可以成功输出结果。

Read More
post @ 2023-12-23

信息安全数学基础

课程实验报告

实验报告(四)

系 别: 网络空间安全系

班 级: secret!

姓 名: secret!

学 号: secret!

实验时间: 2023年11月15日

指导老师: secret!

湖南大学信息科学与工程学院

  1. 实验内容

  1. 实验目标

理解指数定义和求解思路,理解原根存在判断条件和求解过程,用c++编程实现,并在求解原根时优化算法并测试电脑计算性能。

  1. 实验原理

1.指数

2.原根

  1. 实验设计

实验共分为1个主函数和4个自定义函数。其中,主函数负责部分基本变量定义、判断模数p是否为奇素数以及程序的输入和输出,isOddPrime函数是辅助函数判断模数p是否为奇素数的程序执行前提,Euler函数也是辅助函数求解模数p的欧拉函数在求解指数后可以判断该指数是否为原根,也可在求原根优化时作为循环条件区间值,Exp函数是解答第一问的求指数函数,Prim函数是解答第二问的求模数p所有原根

  1. 定义变量和函数

主函数:

底数:a

模数:p

欧拉函数:elr

指数:ord

存放所有原根的数组roots

isOddPrime函数:

函数参数传入的模数:p

函数返回bool类型:true/false

Euler函数:

函数参数传入的模数:p

计数器:cnt

迭代递增指数:e

Exp函数:

函数参数传入的底数和模数:a和p

迭代递增计数器和返回值:e

存放余数的中间变量:result

Prim函数:

函数参数传入的模数:p

存放所有原根的数组stl容器:prim

欧拉函数:euler

迭代递增的底数g

判断是否为原根bool类型:isPrim

  1. 主函数

主函数负责部分基本变量定义、判断模数p是否为奇素数以及程序的输入和输出。首先读入底数a和模数p,通过调用isOddPrime函数判断p是否为奇素数,如果不是,则直接返回0并结束程序。

然后,通过调用Euler函数计算模p的欧拉函数值,并将结果赋给变量elr。这个中间结果在后面计算中多次用到,所以可以先提前计算出来。打印提示信息和elr结果。

接下来,通过调用Exp函数计算整数a模p的指数,并将结果赋给变量ord。打印提示信息和ord结果。

然后,通过调用Prim函数计算模p的所有原根,并将结果存储在名为roots的vector容器中。然后,使用for循环遍历roots容器中的每个元素,并使用输出流cout打印出每个原根的值。

  1. isOddPrime函数

isOddPrime函数是辅助函数判断模数p是否为奇素数

函数参数传入模数p,首先进行两个条件判断:如果p小于等于1,或者p是偶数,则返回false,因为偶数不可能是素数。 如果以上条件都不满足,那么进入循环。

循环从i=3开始,每次迭代增加2,因为偶数已经在前面的条件判断中排除了。循环条件是i * i <= p,即i的平方小于等于p。

在循环体中,判断p是否能被小于等于其平方根的奇数整除,来确定p是否为奇素数。如果能整除,则p不是素数,返回false。如果循环结束后仍然没有找到能整除p的数,则p是素数,返回true。

  1. Euler函数

Euler函数也是辅助函数求解模数p的欧拉函数在求解指数后可以判断该指数是否为原根,也可在求原根优化时作为循环条件区间值。

函数参数传入模数p,首先声明一个整数变量count,用于计数满足条件的数值。然后,通过一个for循环遍历从1到p-1的所有整数。

在循环体中,通过遍历从1到p-1的整数,计算与p互质的数值的个数,从而得到p的欧拉函数值。具体的通过调用库函数中的__gcd函数计算i和p的最大公约数。如果最大公约数等于1,说明i和p互质,即没有共同的因子,满足欧拉函数的定义。此时,将count加1。

循环结束后,count记录了满足条件的数值的个数,即p的欧拉函数值。将count作为函数的返回值。

  1. Exp函数

Exp函数是解答第一问的求指数函数,程序设计思想参考指数的定义。

函数参数传入底数a和模数p。函数首先声明一个整数变量e,用于记录指数的值,初始值为1。然后,声明一个整数变量result,用于存储a对模p的中中间结果。

通过使用循环来计算a的幂,直到结果等于1为止。在每次循环中,将结果乘以a并对p取模,同时记录循环的次数。最后返回循环的次数,也就是指找到最小的正整数e,使得a^e ≡ 1 (mod p)。

  1. Prim函数

Prim函数是解答第二问的求模数p所有原根,上图展示的优化后的算法,优化过程如下:

如果按照原根存在的充要条件实现需要2个函数和3重for循环。首先PrimeQ函数求解整数p-1的所有素因子,q数组容器存放所有的素因子,PrimeQ函数内部通过双重for循环,外层for循环判断i是否能被p整除,内层for循环再判断因子是否是素数,如果满足就向容器中插入p-1/i

Prime1函数计算所有原根。使用3重for循环,第一层for循环遍历2到小于p的整数,第二层for循环遍历计算的p-1/i,将其依次作为指数,内层for循环累乘p-1/i次。

由此可见2个弊端:3层for循环是立方级别的运算,时间复杂度很高;muti累乘很容易超过数据类型的范围。

优化:考虑原根的性质,即它是指数且小于欧拉函数确定遍历范围,以及原根定义是指数等于欧拉函数确定判断条件;并且考虑用long long存放数据类型。合理灵活运用之前的两个函数:Euler函数的结果和Exp求指数函数。优化后仅用两重循环,降低时间复杂度。

函数接受一个长整型参数p,表示模数。它使用循环来遍历从2到p-1的所有整数,判断每个整数是否为模p的原根。

函数首先声明一个vector类型的变量prim,用于存储找到的所有原根。

接下来,通过一个for循环遍历从2到p-1的所有整数,用变量g表示当前整数,对每个整数进行指数计算调用Exp函数,若结果等于欧拉函数则为原根,插入容器中保存。

最后,将存储原根的prim容器作为函数的返回值。

  1. 实验结果
  2. 教材例5.1.1

题目:教材例5.1.1

输入解释:

依次输入:2 7,分别表示底数a和模数p

输出结果:

模p的欧拉函数是:6

整数a模p的指数是:3但不是原根

模p的所有原根共计2个,列举如下:3 5

与教材结果一致,正确

  1. 教材例5.2.1

题目:教材例5.2.1

输入解释:

依次输入:5 41,分别表示底数a和模数p

输出结果:

模p的欧拉函数是:40

整数a模p的指数是:20但不是原根

模p的所有原根共计16个,列举如下:6 7 11 12 13 15 17 19 22 24 26 28 29 30 34 35

与教材结果一致,正确

  1. 教材例5.2.2

题目:

输入解释:

依次输入:9 43,分别表示底数a和模数p

输出结果:

模p的欧拉函数是:42

整数a模p的指数是:21但不是原根

模p的所有原根共计12个,列举如下:3 5 12 18 19 20 26 28 29 30 33 34

与教材结果一致,正确

  1. 测试电脑计算极限

找到素数表,多次输入尝试,发现输入p=46337时是实验电脑能计算的p的最大值,程序运行能在10秒内运算出结果

......(中间结果)

输入下一个更大的素数p=46349会计算不出结果:

六、总结

本次实验用c++编程实现了求解底数a模p的指数和模p的所有原根。在程序前提是p为奇素数的情况下,故先判断前提并且这里调用了c++的库函数__gcd求解最大公因数;进入程序先计算了模p的欧拉函数,这在判断原根时很有用;按照指数的定义编程求解;原根的求解方式有多种,经尝试发现用定义和性质而不是用原根存在性的充要条件会优化许多,因为可以利用之前的欧拉函数结论和再次调用求指数函数,并且时间复杂度也会明显降低。利用求原根还测试了电脑的性能,发现其极限是计算最大奇素数p=46337的原根。

Read More
post @ 2023-12-23

信息安全数学基础

课程实验报告

实验报告(三)

系 别: 网络空间安全系

班 级: secret!

姓 名: secret!

学 号: secret!

实验时间: 2023年10月30日

指导老师: secret!

湖南大学信息科学与工程学院

  1. 实验内容

  1. 实验目标

理解中国剩余定理,用c++实现并不能调用现有库函数,并在优化时增加初始判断条件

  1. 实验原理

  1. 实验设计

实验共分为1个主函数和2个自定义函数。其中,主函数负责部分基本变量定义、判断中国剩余定理判断条件以及输入和输出,chineseRemainder函数是实现中国剩余定理算法核心部分,extEuclidean函数是实现广义欧几里算法用来求解逆元。

  1. 定义变量和函数

主函数:

数组大小:n

存放模的数组:m[]

存放余数的数组:b[]

广义欧几里得系数:s,t

最大公因数:d

chineseRemainder函数:

最终结果:result

所有模的乘积:M

广义欧几里得系数:x,y

中国剩余定理的M:Mi

extEuclidean函数:

函数参数传入的余数:a

函数参数传入的模:b

广义欧几里得系数:x,y

最大公因数:d

  1. 主函数

主函数负责部分基本变量定义、判断中国剩余定理判断条件以及输入和输出

首先定义数组大小n,存放模的数组m,存放余数的数组b,尽量开大一些;

然后输入数组大小n,循环读入模m的元素,循环读入余数b的元素;

判断输入的模是否互素,通过双重for循环遍历模m数组,调用广义欧几里得函数extEuclidean的返回值最大公因数d判断,若存在两两不互素即最大公因数d不为1,则输出错误信息并直接返回程序;

若满足模两两互素,则调用中国剩余定理chineseRemainder函数并输出结果。

  1. chineseRemainder函数

函数是实现中国剩余定理算法核心部分

函数参数传入数组大小n,存放模的数组m,存放余数的数组b;

初始化结果result为0,所有模乘积M为1,定义用于广义欧几里得计算的系数x、y;

循环累乘计算出所有模乘积M,方便后续计算中国剩余定理中的Mi

循环逐个计算每一个同余式的结果并累加到最终结果result,Mi计算为所有模乘积M除以当前模m[i],调用extEuclidean函数利用广义欧几里得求解模m[i]的逆元,得到系数x就是逆元,再利用中国剩余定理累乘b*Mi*x,此时及时对M取模使得结果不会太大超出范围;

将result+模M再取模M 的处理是保证结果result总为正数,理由是在广义欧几里得算出的逆元x没有取正数处理,所以求出的逆元可能是一个负数;

返回最终结果result。

  1. extEuclidean函数

函数是实现广义欧几里算法用来求解逆元

利用递归的思想迭代求解广义欧几里得系数x和y,递归出口是余数b为0;

接受两个参数 a 和 b,表示要计算的两个整数。还接受两个引用参数 x 和 y,用于返回计算结果。

首先检查 b 是否为0。如果是0,说明 a 是最大公约数,此时将 x 设置为1,y 设置为0,并直接返回。

如果 b 不为0,那么函数会递归调用自身,传入参数 b 和 a 除以 b 的余数 a % b,并接收返回的结果 x和 y。

通过递归调用,函数计算出最大公约数d,并将它们存储在传入的引用参数 x 和 y 中,函数迭代y的值并返回最大公因数d

  1. 实验结果
  2. 物不知数

题目:

输入解释:

依次输入:n=3;模m数组:3,5,7;余数b数组:2,3,2

输出结果:

23,与教材结果一致,表示最少有这么多物品

  1. 韩信点兵之二

题目:

输入解释:

依次输入:n=4;模m数组:5,6,7,11;余数b数组:1,5,4,10

输出结果:

2111人,与教材结果一致,表示最少有这么多兵

  1. 作业8

题目:

输入解释:

依次输入:n=5;模m数组:2,3,5,7,11;余数b数组:1,1,1,1,0

输出结果:

2101,经验算:2101/11=191,2101-1=2*3*5*7*10,即2|2101-1,3|2101-1,5|2101-1,7|2101-1

  1. 模不互素的情况

设计最后一个模数只与倒数第二个模数不互素,这样双重for循环判断模是否互素会遍历模m的所有元素,时间是n(n+1)/2。虽然调用extEuclidean函数使用递归实现,但程序反应很快看不出延时

输入解释:

依次输入:n=15;模m数组:99,100,101,97,89,79,73,47,43,23,29,17,19,13,169;余数b数组:15,14,13,12,11,10,9,8,7,6,5,4,3,2,1

输出结果:

模不互素:13和169的最大公因数是13

打印错误信息,表示模之间存在两两不互素情况,没有严格遵守中国剩余定理的使用条件,直接退出程序

六、总结

本次实验在不调用库函数的情况下用c++实现中国剩余定理,利用到实验一中的广义欧几里得算法求解最大公因数判断互素条件以及求解逆元,解决一次同余方程组的求解问题。

Read More
post @ 2023-12-23

信息安全数学基础

课程实验报告

实验报告(二)

系 别: 网络空间安全系

班 级: secret!

姓 名: secret!

学 号: secret!

实验时间: 2023年10月25日

指导老师: secret!

湖南大学信息科学与工程学院

一、实验内容

编程求解模平方计算法

二、实验目标

理解模平方计算法并会用c++编程求解,进一步改进优化

  1. 实验原理

  1. 实验设计

实验共分为主函数和4个自定义函数,

Longlong类型解释:

变量均定义为long long而不是一味的int的原因是,为了解决指数很大的情况,例如老师上课随机举例的日期如20231025等等,进而存放二进制表示的数组也要开大一些

自定义函数解释:

decToBin函数作用是将十进制数转换为二进制数

calcBit函数的作用是计算一个数的二进制位数

printBin函数的作用是打印存储在数组中的二进制数

calMod函数的作用是计算模幂运算

其中最核心的部分是calMod函数,按照模平方算法的思想进行代码实现,并输出时保证计算过程清晰可见

  1. 定义变量和函数

主函数:

long long类型变量:

指数exponent

底数base

二进制位数bit

模mod

二进制表示数组binary[32]

decToBin函数:

long long类型变量:

除2余数i

除2商j

二进制表示数组的下标k

calcBit函数:

long long类型:

十进制整数n

循环变量最终表示二进制位数i

printBin函数:

long long类型:

循环打印变量且为数组下标i

calcMod函数:

long long类型:

算法中的a不断迭代result

算法中的b不断迭代base

数组下标j

  1. 主函数

首先声明了变量exponent、base、bit和mod,以及一个存储二进制数的数组binary[]有32位。然后,函数打印欢迎信息和输入提示信息。接下来,函数使用scanf函数从用户输入中读取指数、底数和模数。然后,函数打印指数的二进制表示,并调用calcBit函数计算二进制位数,并调用printBin函数打印存储的二进制数。最后,函数调用calcMod函数进行模幂运算。函数返回0,表示程序正常结束。

  1. decToBin函数

此函数的作用是将十进制数转换为二进制数。函数参数是一个十进制数n和一个存储二进制数的数组binary[]作为参数。函数使用循环将十进制数n转换为二进制数,并将每一位二进制数存储在数组binary[]中。然后,函数使用循环打印二进制数,并在每4位之间插入一个空格。最后,函数返回0。

  1. calcBit函数

此函数的作用是计算一个数的二进制位数。函数的参数是十进制整数n。函数使用循环逐渐增加一个变量i的值,直到找到一个i,使得2的i次方大于n。然后,函数返回i。

其实还有一种方法,就是遍历已求得的二进制数组,找到最高位为1对应的数组下标,加1就是二进制位数,不同的是函数传参是binary数组而不是十进制整数n

  1. printBin函数

此函数的作用是打印存储在数组中的二进制数。函数的参数是存储二进制数的数组binary[]。函数使用循环打印数组中的每一位二进制数,并在每4位之间插入一个空格。最后,函数返回0。

  1. calMod函数

此函数的作用是计算模幂运算。函数的参数有指数exponent、底数base、模数mod、二进制位数bit和存储二进制数的数组binary[]。函数使用循环根据二进制数的每一位进行模幂运算,并打印每一步的计算过程。最后,函数返回计算结果。

具体的,函数严格模拟了模平方算法整个过程,刚开始令a取1,b取底数;如果二进制当前位为0,那么ai=a(i-1),否则ai=a(i-1)*bi;bi=b(i-1)^2;直到计算完所有二进制位数,输出a的当前结果就是代求的余数结果

  1. 实验结果
  2. 教材2.5.6

计算12996^227(mod37909)

输入:227 12996 37909

输入解释:依次输入指数227、底数12996、模数37909

输出结果解释:

227的二进制表示是1110 0011共8位,倒序存储在数组中(二进制表示的低位对应数组低位),由此可知共循环计算8次,按照模平方算法,最后结果余数为7775。

  1. 作业2.5教材P89 24

计算3^1000000(mod 7)

输入:

1000000 3 7

输入解释:

依次输入指数1000000、底数3、模数7

输出结果解释:

1000000的二进制表示是1111 0100 0010 0100 0000共20位,倒序存储在数组中(二进制表示的低位对应数组低位),由此可知共循环计算20次,按照模平方算法,最后结果余数为5。

  1. 随机出题

计算1234^20231025(mod 56789)

输入:

20231025 1234 56789

输入解释:

依次输入指数20231025、底数1234、模数56789

输出结果解释:

20231025的二进制表示是1 0011 0100 1011 0011 0111 0001共25位,倒序存储在数组中(二进制表示的低位对应数组低位),由此可知共循环计算25次,按照模平方算法,最后结果余数为33926。

六、总结

本次实验用c++编程实现了模平方计算方法。自定义了几个辅助函数用于前期的处理准备,将指数十进制转为二进制,由于指数可能较大,所以用一个数组保存二进制的每一位,值得注意的是,需要倒序把放入数组中方便后续的模平方计算。代码严格按照模平方计算过程模拟实现。如果二进制当前位为0,那么ai=a(i-1),否则ai=a(i-1)*bi;bi=b(i-1)^2;直到计算完所有二进制位数,输出a的当前结果就是代求的余数结果。

Read More
post @ 2023-12-22

关于这个博客的处女作hhh

现在是2023年12月22日 23点56分,咳咳,虽然现在是紧张的考试周,明天就是一年一度的考研了(虽然我现在还是大三还不用考),但是!总之学校周围走到哪都感到沉闷的低气压…
今天在自习室和图书馆看了一天算法设计与分析,准备晚上再看看编译原理,但是我真的好困zzz(虽然下午已经睡过了,但晚上还是好困…是不是暴露了我是INTP哈哈)。
从昨晚到现在终于挤出点时间做自己想做的事情,制作我的第一个网站!!昨晚照着网上“三分钟教程”结果部署了快三小时(我知道我很菜啦!特别是在网络这块…因为上学期网络没学好本能有些畏惧排斥:C)但是无论如何我还是建好啦!精心挑选的我喜欢的主题!
感谢每一位点进来的uu!如果我的博客能给你哪怕一丢丢帮助我都很开心啦!让我们一起进步!加油!计算机er!

Read More
post @ 2023-12-21

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

Read More
⬆︎TOP